package algotithm.leetcode.dfs.test1631;

/**
 * @author zhouyanxiang
 * @Date 2021-01-2021/1/29-10:18
 */
public class Main {

    public static void main(String[] args) {
        Main m = new Main();
        int[][] heights = {{1,2,2},{3,8,2},{5,3,5}};
        int minimumEffortPath = m.minimumEffortPath(heights);
        System.out.println(minimumEffortPath);
    }

    int d[][] = new int[][]{{0,1},{0,-1},{1,0},{-1,0}};
    public int minimumEffortPath(int[][] heights) {
        int col = heights.length;
        int row = heights[0].length;
        int low = 0;
        int high = 1000000;
        while(low<high){
            int mid = (low+high)/2;
            //如果说按当前体力值可以走到右下角，那么就缩小体力值上限
            if(dfs(0,0,new boolean[col][row],mid,heights)){
                high = mid;
//                System.out.println(high);
            } else {
                //如果说按当前设定体力值走不到右下角，提高体力值下限
                low = mid + 1;
            }
        }
        return low;
    }
    public boolean dfs(int x,int y,boolean visited[][],int target,int h[][]){
        if (x == h.length-1 && y == h[0].length-1) {
            return true;
        }
        for(int i=0;i<4;i++){
            int newx = x + d[i][0];
            int newy = y + d[i][1];
            if(newx>=0&&newx<=h.length-1&&newy>=0&&newy<=h[0].length-1&&!visited[newx][newy]&&Math.abs(h[x][y]-h[newx][newy])<=target){
                visited[newx][newy] = true;
                if(dfs(newx,newy,visited,target,h)){
                    return true;
                }
            }
        }
        return false;
    }
}

